public class TestDemo2 {
    //你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
    // 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

    public int rob(int []nums){
        //第一种
        if(nums==null||nums.length==0){
            return 0;
        }
        int [][]dp=new int [nums.length][2];
        dp[0][0]=0;
        dp[0][1]=nums[0];
        for(int i=1;i<nums.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]);
            dp[i][i]=dp[i-1][0]+nums[i];
        }return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);
    }//第二种(比较好理解）
    public int rob1(int []nums){
        if(nums==null||nums.length==0){
            return 0;
        }
        int length=nums.length;
        if(length==0){
            return nums[0];
        }
        int []dp=new int [length];
        dp[0]=nums.length;//偷一间房的情况
        dp[1]=Math.max(nums[0],nums[1]);//偷两间房的情况，选其中偷的最多钱的房间
        int i=0;
        for( i=2;i<length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);//偷前i(i>2)次房间的最大利润
        }return dp[length-1];
    }//第三种
    public int rob2(int []nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int dp0 = 0;
        int dp1 = nums[0];
        for (int i = 1; i < length; i++) {
            int tem = Math.max(dp0, dp1);//取偷前一次家的最大值
            dp1 = dp0 + nums[i];//目的是间镉相加
            dp0 = tem;//保留最大值
        }
        return Math.max(dp0, dp1);//最后一次偷的最大值
    }



    //你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    //返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
    //第一种
    public static int maxProfit1(int prices[]) {
        if(prices==null||prices.length==0){
            return 0;
        }
        int cur=0;                           //最大利润间的数字等于它们相邻两个数的差，所以可以用
        int max=0;                           // //相邻两个数的差值求最大利润。
        for(int i=1;i<prices.length;i++){
            cur=Math.max(cur,0)+prices[i]-prices[i-1];//如果利润是负的，就要忽略前面，从能求出两个相邻两个数的正数
            max=Math.max(max,cur);                    //开始计算。
        }return max;
    }
//第二种
    public static void main2(String[] args) {
        int[] prices={7,1,5,3,6,4};
        System.out.println(maxProfit(prices));
    }
    public static int maxProfit3(int prices[]){
        if(prices==null||prices.length==0){
            return 0;
        }
        int minprice=Integer.MAX_VALUE;//为什么要取最大值的目的是，为下面的条件做铺垫
        int maxprofit=0;               //只要大于最小值就要进行交换
        for(int i=0;i<prices.length;i++){
            if(prices[i]<minprice){
                minprice=prices[i];//找到最小的数
            }
            else if(prices[i]-minprice>maxprofit){//使用else if的目的是从最小数的后面的数开始找
                maxprofit=prices[i]-minprice; //求出最大利润
            }
        }return maxprofit;
    }
    //第三种
    public static int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0)
            return 0;
        int maxPro = 0;//记录最大利润
        int min = prices[0];//记录数组中访问过的最小值
        for (int i = 1; i < prices.length; i++) {
            min = Math.min(min, prices[i]);//找到最小值后，从最小值后面找到最大利润
            maxPro = Math.max(prices[i] - min, maxPro);
        }
        return maxPro;

    }
    public int maxSubArray(int []num){
        if(num==null||num.length==0){
            return 0;
        }
        int cur=num[0];
        int max=cur;
        for(int i=1;i<num.length;i++){
            cur=Math.max(cur,0)+num[i];
            max=Math.max(max,cur);
        }return max;
    }
    public int climStairs(int n){
        if(n<1){
            return 1;
        }
      int []dp=new int [n+1];
      dp[1]=1;
      dp[2]=2;
      for(int i=3;i<=n;i++){
          dp[i]=dp[i-2]+dp[i-1];
      }return dp[n];
    }
    }

